Branch and bound crossed with GA to solve hybrid flowshops
Identifieur interne : 00B261 ( Main/Exploration ); précédent : 00B260; suivant : 00B262Branch and bound crossed with GA to solve hybrid flowshops
Auteurs : M.-C. Portmann [France] ; A. Vignier [France] ; D. Dardilhac [France] ; D. Dezalay [France]Source :
- European Journal of Operational Research [ 0377-2217 ] ; 1998.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
- Teeft :
- Algorithm, Assignment decision variables, Assignment parts, Average computation time, Best solution, Better solution, Bottleneck stage, Chromosome, Circle node, Complete solutions, Completion time, Current node, Elsevier science, European journal, Genetic algorithm, Genetic algorithms, Good genitors, Heuristic, Hunsucker, Hybrid, Inverse problem, Last stage, Maximum deviation, Mutation algorithm, Mutation operators, Nancy cedex, Node, Operational research, Operations research, Optimal solution, Order decision variables, Order parts, Owshop, Owshop problems, Owshop scheduling problem, Owshop scheduling problems, Parameter value, Portmann, Precedence matrix, Processing time, Processing times, Scheduling, Search tree, Shop scheduling, Square node, Square nodes, Upper bounds.
Abstract
Abstract: This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.
Url:
DOI: 10.1016/S0377-2217(97)00333-0
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000708
- to stream Istex, to step Curation: 000703
- to stream Istex, to step Checkpoint: 002493
- to stream Main, to step Merge: 00B983
- to stream PascalFrancis, to step Corpus: 000B90
- to stream PascalFrancis, to step Curation: 000C84
- to stream PascalFrancis, to step Checkpoint: 000B60
- to stream Main, to step Merge: 00BB82
- to stream Main, to step Curation: 00B261
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Branch and bound crossed with GA to solve hybrid flowshops</title><author><name sortKey="Portmann, M C" sort="Portmann, M C" uniqKey="Portmann M" first="M.-C." last="Portmann">M.-C. Portmann</name></author><author><name sortKey="Vignier, A" sort="Vignier, A" uniqKey="Vignier A" first="A." last="Vignier">A. Vignier</name></author><author><name sortKey="Dardilhac, D" sort="Dardilhac, D" uniqKey="Dardilhac D" first="D." last="Dardilhac">D. Dardilhac</name></author><author><name sortKey="Dezalay, D" sort="Dezalay, D" uniqKey="Dezalay D" first="D." last="Dezalay">D. Dezalay</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:1F3EF4DE4B181191F53D5E2837C2844407BB6F0E</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1016/S0377-2217(97)00333-0</idno><idno type="url">https://api.istex.fr/ark:/67375/6H6-S8ZWHG72-X/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000708</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000708</idno><idno type="wicri:Area/Istex/Curation">000703</idno><idno type="wicri:Area/Istex/Checkpoint">002493</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002493</idno><idno type="wicri:doubleKey">0377-2217:1998:Portmann M:branch:and:bound</idno><idno type="wicri:Area/Main/Merge">00B983</idno><idno type="wicri:source">INIST</idno><idno type="RBID">Pascal:98-0455270</idno><idno type="wicri:Area/PascalFrancis/Corpus">000B90</idno><idno type="wicri:Area/PascalFrancis/Curation">000C84</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000B60</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B60</idno><idno type="wicri:doubleKey">0377-2217:1998:Portmann M:branch:and:bound</idno><idno type="wicri:Area/Main/Merge">00BB82</idno><idno type="wicri:Area/Main/Curation">00B261</idno><idno type="wicri:Area/Main/Exploration">00B261</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Branch and bound crossed with GA to solve hybrid flowshops</title><author><name sortKey="Portmann, M C" sort="Portmann, M C" uniqKey="Portmann M" first="M.-C." last="Portmann">M.-C. Portmann</name><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>CRIN – CNRS URA 262, Ecole des Mines de Nancy, Parc de Saurupt, 54 042 Nancy Cedex</wicri:regionArea><wicri:noRegion>54 042 Nancy Cedex</wicri:noRegion><wicri:noRegion>54 042 Nancy Cedex</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Vignier, A" sort="Vignier, A" uniqKey="Vignier A" first="A." last="Vignier">A. Vignier</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis, 37200 Tours</wicri:regionArea><placeName><region type="region" nuts="2">Centre-Val de Loire</region><region type="old region" nuts="2">Région Centre</region><settlement type="city">Tours</settlement></placeName></affiliation><affiliation wicri:level="3"><country wicri:rule="url">France</country><wicri:regionArea>Corresponding author. Address: CRIN, Batiment LORIA, Campus Scientifique, BP 239, F-54500 Vandoeuvre les Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation></author><author><name sortKey="Dardilhac, D" sort="Dardilhac, D" uniqKey="Dardilhac D" first="D." last="Dardilhac">D. Dardilhac</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis, 37200 Tours</wicri:regionArea><placeName><region type="region" nuts="2">Centre-Val de Loire</region><region type="old region" nuts="2">Région Centre</region><settlement type="city">Tours</settlement></placeName></affiliation></author><author><name sortKey="Dezalay, D" sort="Dezalay, D" uniqKey="Dezalay D" first="D." last="Dezalay">D. Dezalay</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis, 37200 Tours</wicri:regionArea><placeName><region type="region" nuts="2">Centre-Val de Loire</region><region type="old region" nuts="2">Région Centre</region><settlement type="city">Tours</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">European Journal of Operational Research</title><title level="j" type="abbrev">EOR</title><idno type="ISSN">0377-2217</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1998">1998</date><biblScope unit="volume">107</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="389">389</biblScope><biblScope unit="page" to="400">400</biblScope></imprint><idno type="ISSN">0377-2217</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0377-2217</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Branch and bound method</term><term>Flow shop</term><term>Genetic algorithm</term><term>Hybrid model</term><term>Lower bound</term><term>Production system</term><term>Scheduling</term><term>Upper bound</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Algorithme génétique</term><term>Borne inférieure</term><term>Borne supérieure</term><term>Flow shop</term><term>Modèle hybride</term><term>Méthode séparation et évaluation</term><term>Ordonnancement</term><term>Système production</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Assignment decision variables</term><term>Assignment parts</term><term>Average computation time</term><term>Best solution</term><term>Better solution</term><term>Bottleneck stage</term><term>Chromosome</term><term>Circle node</term><term>Complete solutions</term><term>Completion time</term><term>Current node</term><term>Elsevier science</term><term>European journal</term><term>Genetic algorithm</term><term>Genetic algorithms</term><term>Good genitors</term><term>Heuristic</term><term>Hunsucker</term><term>Hybrid</term><term>Inverse problem</term><term>Last stage</term><term>Maximum deviation</term><term>Mutation algorithm</term><term>Mutation operators</term><term>Nancy cedex</term><term>Node</term><term>Operational research</term><term>Operations research</term><term>Optimal solution</term><term>Order decision variables</term><term>Order parts</term><term>Owshop</term><term>Owshop problems</term><term>Owshop scheduling problem</term><term>Owshop scheduling problems</term><term>Parameter value</term><term>Portmann</term><term>Precedence matrix</term><term>Processing time</term><term>Processing times</term><term>Scheduling</term><term>Search tree</term><term>Shop scheduling</term><term>Square node</term><term>Square nodes</term><term>Upper bounds</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Centre-Val de Loire</li><li>Grand Est</li><li>Lorraine (région)</li><li>Région Centre</li></region><settlement><li>Tours</li><li>Vandœuvre-lès-Nancy</li></settlement></list><tree><country name="France"><noRegion><name sortKey="Portmann, M C" sort="Portmann, M C" uniqKey="Portmann M" first="M.-C." last="Portmann">M.-C. Portmann</name></noRegion><name sortKey="Dardilhac, D" sort="Dardilhac, D" uniqKey="Dardilhac D" first="D." last="Dardilhac">D. Dardilhac</name><name sortKey="Dezalay, D" sort="Dezalay, D" uniqKey="Dezalay D" first="D." last="Dezalay">D. Dezalay</name><name sortKey="Portmann, M C" sort="Portmann, M C" uniqKey="Portmann M" first="M.-C." last="Portmann">M.-C. Portmann</name><name sortKey="Vignier, A" sort="Vignier, A" uniqKey="Vignier A" first="A." last="Vignier">A. Vignier</name><name sortKey="Vignier, A" sort="Vignier, A" uniqKey="Vignier A" first="A." last="Vignier">A. Vignier</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B261 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B261 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:1F3EF4DE4B181191F53D5E2837C2844407BB6F0E
|texte= Branch and bound crossed with GA to solve hybrid flowshops
}}
| This area was generated with Dilib version V0.6.33. |  |